package com.cat.DataStructure04;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/map-sum-pairs/description/
 * @create 2025/11/26 15:28
 * @since JDK17
 */

class MapSum {
    static int N = ((int) 1e3), cnt = 1;
    static int[][] tree = new int[N][26];
    static int[] pass = new int[N];
    static Map<String, Integer> map = new HashMap<>();
    public MapSum() {
        for (int i = 1; i <= cnt; i++) {
            Arrays.fill(tree[i], 0);
            pass[i] = 0;
        }
        map.clear();
        cnt = 1;
    }

    public void insert(String key, int val) {
        int cur = 1, t = val;
        t -= map.getOrDefault(key, 0);
        map.put(key, val);
        for (int i = 0, path; i < key.length(); i++) {
            path = key.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
            pass[cur] += t;
        }
    }

    public int sum(String prefix) {
        int cur = 1;
        for (int i = 0, path; i < prefix.length(); i++) {
            path = prefix.charAt(i) - 'a';
            if (tree[cur][path] == 0) { // 断了
                return 0;
            }
            cur = tree[cur][path];
        }
        return pass[cur];
    }
}



